package 算法;

public class 加油站 {

    public static void main(String[] args) {
        new 加油站().maxSizeSlices(new int[]{1,2,3,4,5,6});
    }

    public int maxSizeSlices(int[] slices) {
        int[] a = new int[slices.length-1];
        System.arraycopy(slices,1,a,0,slices.length-1);
        int[] b = new int[slices.length-1];
        System.arraycopy(slices,0,b,0,slices.length-1);
        return Math.max(conSize(a),conSize(b));
    }
    //返回slices选取的最大值
    public int conSize(int[] slices){
        int count = (slices.length+1) / 3;
        int dp[][] = new int[slices.length+1][count+1];

        for (int i = 1; i <= slices.length; i++) {
            for (int j = 1; j <= count;j++){
                dp[i][j] = Math.max(dp[i-1][j],slices[i-1]+(i-2 > 0 ?dp[i-2][j-1]:0));
            }
        }
        return dp[dp.length-1][count];
    }
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int youliang = 0,xiaohao = 0;
        int len = gas.length;
        int i,j;
        for (i = 0; i < len; i++){
            youliang = xiaohao = 0;
            for (j = 0; j < len; j++){
                youliang += gas[(i+j)%len];
                xiaohao += cost[(i+j)%len];
                if(xiaohao > youliang) break;
            }
            if(j == len) return i;
        }
        return -1;
    }
}
